{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Extending AES-128 Attacks to AES-256\n",
    "\n",
    "Many of the labs discuss attacks on AES-128 encryption. It turns out that its big brother, AES-256, can be attacked by extending the same attacks. This page discusses AES-256 and how to reuse an AES-128 attack to obtain the key. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## AES-128 and AES-256\n",
    "\n",
    "In AES-128, we used the following steps to encrypt 16 bytes of plaintext: \n",
    "\n",
    "1. Use a 16 byte key to generate a key schedule, which is 176 bytes long (11 words, 16 bytes per round)\n",
    "1. Put the 16 bytes of plaintext into a 4x4 state matrix\n",
    "1. Combine the 1st round key and the state matrix\n",
    "1. Apply 10 rounds of transformations to the state, involving the key schedule\n",
    "1. Retrieve 16 bytes of ciphertext from the state matrix\n",
    "\n",
    "This looks like:\n",
    "\n",
    "![](img/aes_operations.png)\n",
    "\n",
    "AES-256 is very similar. It looks like (differences with AES-128 in **bold**):\n",
    "\n",
    "1. **Use a 32 byte key to generate a key schedule, which is 240 bytes long (15 words, 16 bytes per round)**\n",
    "1. Put the 16 bytes of plaintext into a 4x4 state matrix\n",
    "1. Combine the 1st round key and the state matrix\n",
    "1. **Apply 14 rounds of transformations to the state, involving the key schedule**\n",
    "1. Retrieve 16 bytes of ciphertext from the state matrix\n",
    "\n",
    "Most of this algoritm is the same. In fact, we can simply repeat our AES-128 attack to get the first half of the key!\n",
    "\n",
    "### Getting the Second Half of the Key\n",
    "\n",
    "Getting the second half of the key is similarly simple: all we need to do is use our newly found first round key to calculate the state matrix at the output of that first `MixColumns` operation. From there, we're basically in the same spot as before: we've got an `AddRoundKey` operation with an unknown key and a `SubBytes` lookup. Repeat the attack, using the calculated state matrix instead of the plaintext (and make sure your traces also have this next `AddRoundKey`/`SubBytes` in it as well) and you'll recover the second half of the key!\n",
    "\n",
    "## AES-256 Decryption\n",
    "\n",
    "Not all devices perform an AES encryption - some devices perform a decryption instead. All of those AES operations have an inverse. The last three operations of AES are (there's no `MixColumns` in the last round:\n",
    "\n",
    "1. `SubBytes`\n",
    "1. `ShiftRows`\n",
    "1. `AddRoundKey`\n",
    "\n",
    "So the start of decryption looks like:\n",
    "\n",
    "1. `AddRoundKey`\n",
    "1. `InvShiftRows`\n",
    "1. `InvSubBytes`\n",
    "\n",
    "Ignore the `InvShiftRows` (it only changes which byte of ciphertext goes with which byte of key, it doesn't actually affect the attack), and we've basically got the same situation as with encryption: an `AddRoundKey` followed by an `InvSubBytes` lookup. Replace the plaintext with the ciphertext, and the `SBox` with `InvSBox` in your Hamming weight calculation, and you'll recover the first 16 bytes of the decryption key.\n",
    "\n",
    "### Getting the Second Half of the Key\n",
    "\n",
    "Getting the second half of the key appears not to be as simple as with encryption. After that `InvSubBytes`, we've got:\n",
    "\n",
    "1. `AddRoundKey`\n",
    "1. `InvMixColumns`\n",
    "1. `InvShiftRows`\n",
    "1. `InvSBox`\n",
    "\n",
    "This time there's an `InvMixColumns` in there, which combines 4 bytes of state together. Suddenly, we're not attacking a single byte at a time (256 values), we're attacking 4 bytes (4 294 967 296 values)! To solve this, let's try writing the last step as an equation:\n",
    "\n",
    "$$X_{13}= \\text{SubBytes}^{-1}\\left(\\text {MixColumns }^{-1}\\left(\\text {ShiftRows }^{-1}\\left(X_{14} \\oplus K_{13}\\right)\\right)\\right)$$\n",
    "\n",
    "where $X_{14}$ is the output of round 14, $K_{13}$ is the 16 byte round key for round 13, and $X_{13}$ is the output of round 13 (our attack point). `MixColumns` is actually a linear function; that is:\n",
    "\n",
    "$$\\text{MixColumns(A+B)} = \\text{MixColumns(A)} + \\text{MixColumns(B)}$$\n",
    "\n",
    "Using this property, we can write down the hypothetical key for round 13, which is:\n",
    "\n",
    "$$K_{13}' = \\text{MixColumns}^{-1}(\\text{ShiftRows}^{-1}(K_{13}))$$\n",
    "\n",
    "and we can use this hypothetical key to calculate the output as:\n",
    "\n",
    "$$\\left.X_{13}=\\text { SubBytes }^{-1}(\\text {MixColumns }^{-1}\\left(\\text {ShiftRows }^{-1}\\left(X_{14}\\right)\\right) \\oplus K_{13}^{\\prime}\\right)$$\n",
    "\n",
    "We know all of $X_{14}$ and can therefore do the `InvMixColumns` and `InvShiftRows`, meaning we're once again at an `AddRoundKey` followed by an `InvSubBytes`! Then, we can recover the actual round key by calculating $$K_{13} = \\text{MixColumns}(\\text{ShiftRows}(K_{13}'))$$\n",
    "\n",
    "Once you've got the 14th and 13th round keys, you can calculate the rest of the key schedule, including the 1st and 2nd round keys.\n",
    "\n",
    "\n",
    "#### Alternative Decryption\n",
    "\n",
    "You might have noticed an oddity about the decryption process in the AES block diagram; the `InvMixColumns` and `AddRoundKey` operations are switched! Since `MixColumns` is linear, you can apply `MixColumns` to the round key and swap the operations. AES decryption is sometimes written in this way to make it look more like the encryption process."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
